#include "LeBSTExt.h"

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <time.h>
#include <vector>
#include <set>
#include <iterator>

#define BST_TREE_PERFORMANCE_TEST_WITH_SET 1

struct Comparer // works like std::greater<int>
{
	bool operator()(int one, int two) const { return one > two; }
};

void testScenarioFromGuideBook()
{
	// arrange
	LeBST<int> tree;

	// act
	assert(tree.insert(4));
	assert(tree.insert(7));
	assert(tree.insert(2));
	assert(tree.insert(5));
	assert(tree.insert(3));
	assert(tree.insert(1));
	assert(tree.erase(2));

	// assert
	assert(tree.getVersionNumber() == 7);

	assert(tree.find(4));
	assert(tree.find(7));
	assert(!tree.find(2)); // not found
	assert(tree.find(5));
	assert(tree.find(3));
	assert(tree.find(1));

	assert(tree.find(2, 6)); // before erasing

	LeBST<int>::iterator i = tree.begin();
	assert(*i++ == 1);
	assert(*i++ == 3);
	assert(*i++ == 4);
	assert(*i++ == 5);
	assert(*i == 7);
	assert(++i == tree.end());
}

void testScenarioChainedReplacing()
{
	//arrange
	LeBST<int> tree;

	//act
	assert(tree.insert(4));
	assert(tree.insert(6));
	assert(tree.insert(8));
	assert(tree.insert(10));
	// inserting 7 should cause chained replacing of 8, 6 and root 4
	assert(tree.insert(7));

	//assert
	LeBST<int>::iterator i = tree.begin();
	assert(*i++ == 4);
	assert(*i++ == 6);
	assert(*i++ == 7);
	assert(*i++ == 8);
	assert(*i == 10);
	assert(++i == tree.end());
}

void testExtremeCases()
{
	LeBST<int> tree;
	int value = 0;

	// empty tree:
	assert(!tree.find(value)); // empty tree
	assert(!tree.find(value, -1)); // incorrect version, empty tree
	assert(!tree.erase(value)); // non-existant node

	// inserting (one element)
	assert(tree.insert(value)); // first element, ok

	assert(!tree.find(value, 0)); // value 0 is from version 1
	assert(tree.find(value, 100)); // found
	assert(tree.find(value)); // found

	// erasing (no elements)
	assert(tree.erase(value)); // erased

	assert(tree.find(value, 1)); // found
	assert(!tree.find(value, 100)); // already erased
	assert(!tree.find(value)); // already erased

	assert(!tree.erase(value)); // non-existant node
}

void testDuplicates()
{
	LeBST<int> tree;
	int value = 0;

	assert(tree.insert(value));
	assert(!tree.insert(value)); // duplicate

	assert(tree.erase(value)); // deleting root, none left
	assert(!tree.find(value)); // not found

	assert(tree.insert(value)); // re-inserting as root
	assert(!tree.insert(value)); // duplicate
	assert(tree.find(value));
}

void testIterator()
{
	LeBST<int> tree;

	assert(tree.insert(4));
	assert(tree.insert(7));
	assert(tree.insert(2));
	assert(tree.insert(5));
	assert(tree.insert(3));
	assert(tree.insert(1));
	assert(tree.erase(2));

	// test for latest version
	LeBST<int>::iterator i = tree.begin();
	assert(*i++ == 1);
	assert(*i++ == 3);
	assert(*i++ == 4);
	assert(*i++ == 5);
	assert(*i == 7);
	assert(++i == tree.end());

	// test for version 6 (before erasing 2)
	i = tree.begin(6);
	assert(*i++ == 1);
	assert(*i++ == 2);
	assert(*i++ == 3);
	assert(*i++ == 4);
	assert(*i++ == 5);
	assert(*i == 7);
	assert(++i == tree.end(6));

	// test for version 1
	i = tree.begin(1);
	assert(*i == 4);
	assert(++i == tree.end(1));

	// test for an incorrect version
	i = tree.begin(-1);
	assert(i == tree.end(-1));

	// example of a loop
	for (LeBST<int>::iterator it = tree.begin(); it != tree.end(); ++it)
	{
		cout << *it << endl;
	}
}

void testInsertUsingModFlags()
{
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);

		//act
		tree.insert(1); // modifi root
		tree.insert(2); // modifi 1
		
		//assert
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 1);
		assert(*i == 2);
		assert(++i == tree.end());
	}
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);

		//act
		tree.insert(2); // modifi root
		tree.insert(1); // modifi 2
		
		//assert
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 1);
		assert(*i == 2);
		assert(++i == tree.end());
	}
}

void testInsertWithReplace()
{
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(-2); // modifi root
		tree.insert(-1); // modifi -2
		
		//act
		tree.insert(-3); // replace -2 and root 0
		
		//assert
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == -3);
		assert(*i++ == -2);
		assert(*i++ == -1);
		assert(*i == 0);
		assert(++i == tree.end());
	}
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(-2); // modifi root
		tree.insert(-3); // modifi -2

		//act
		tree.insert(-1); // replace -2 and root 0

		//assert
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == -3);
		assert(*i++ == -2);
		assert(*i++ == -1);
		assert(*i == 0);
		assert(++i == tree.end());
	}
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(2); // modifi root
		tree.insert(3); // modifi 2

		//act
		tree.insert(1); // replace 2 and root 0

		//assert
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 1);
		assert(*i++ == 2);
		assert(*i == 3);
		assert(++i == tree.end());
	}
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(2); // modifi root
		tree.insert(1); // modifi 2

		//act
		tree.insert(3); // replace 2 and root 0

		//assert
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 1);
		assert(*i++ == 2);
		assert(*i == 3);
		assert(++i == tree.end());
	}
}

void testEraseLeafUsingModFlags()
{
	{ 
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(2); // modifi root
		tree.insert(1); // modifi 2
		tree.insert(3); // replace 2 and root 0

		//act
		tree.erase(1); // erase using mod flags

		//assert
		assert(!tree.find(1));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 2);
		assert(*i == 3);
		assert(++i == tree.end());
	}
	{
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(2); // modifi root
		tree.insert(1); // modifi 2
		tree.insert(3); // replace 2 and root 0

		//act
		tree.erase(3); // erase using mod flags

		//assert
		assert(!tree.find(3));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 1);
		assert(*i == 2);
		assert(++i == tree.end());
	}
}

void testEraseLeafWithReplace()
{
	{ 
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(-1); // modifi root
		tree.insert(-2); // modifi -1

		//act
		tree.erase(-2); // erase with replacing -1 and root 0

		//assert
		assert(!tree.find(-2));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == -1);
		assert(*i == 0);
		assert(++i == tree.end());
	}
	{ 
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(-2); // modifi root
		tree.insert(-1); // modifi -2

		//act
		tree.erase(-1); // erase with replacing -2 and root 0

		//assert
		assert(!tree.find(-1));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == -2);
		assert(*i == 0);
		assert(++i == tree.end());
	}
	{ 
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(1); // modifi root
		tree.insert(2); // modifi 1

		//act
		tree.erase(2); // erase with replacing 1 and root 0

		//assert
		assert(!tree.find(2));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i == 1);
		assert(++i == tree.end());
	}
	{ 
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(2); // modifi root
		tree.insert(1); // modifi 2

		//act
		tree.erase(1); // erase with replacing 2 and root 0

		//assert
		assert(!tree.find(1));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i == 2);
		assert(++i == tree.end());
	}
}

void testEraseParentUsingModFlags()
{
	{ 
		//arrange
		LeBST<int> tree;
		tree.insert(0);
		tree.insert(5); // modifi root
		tree.insert(4); // modifi 5
		tree.insert(2); // modifi 4
		tree.insert(1); // modifi 2
		tree.insert(3); // replace 2, 4, 5 and root 0

		/* prepared a tree with no mod flags in current version
		0
		   \
		     5
		     /
		    4
		   /
		  2 << deleting 2
	     /\
		 1 3
		*/

		//act
		tree.erase(2); // erase using mod flags

		/* after erasing
		0
		   \
		     5
		     /
		    4 (modified)
		   /
		  3
	     /
		 1
		*/

		//assert
		assert(!tree.find(2));
		
		LeBST<int>::iterator i = tree.begin();
		assert(*i++ == 0);
		assert(*i++ == 1);
		assert(*i++ == 3);
		assert(*i++ == 4);
		assert(*i == 5);
		assert(++i == tree.end());
	}
}

void performanceTestsOnStrings(string dataSource)
{
	// prepare random data:
	cout << endl << "Preparing data from: " << dataSource << endl;

	ifstream in(dataSource, std::ios::in | std::ios::binary);
	vector<string> vec((istream_iterator<string>(in)), istream_iterator<string>());
	in.close();

	random_shuffle(vec.begin(), vec.end());

	clock_t start, end;
	cout << endl << "Performance tests for inserting " << vec.size() << " strings :" << endl;

#ifdef BST_TREE_PERFORMANCE_TEST_WITH_SET
	{ // run performance tests on set<string>:
		set<string> otherTree;

		start = clock();
		for (vector<string>::iterator i = vec.begin(); i != vec.end(); ++i)
		{
			otherTree.insert(*i);
		}
		end = clock();
		cout << "Insert: execution time for set: " << end - start << " [ms]." << endl;

		start = clock();
		for (vector<string>::iterator i = vec.begin(); i != vec.end(); ++i)
		{
			otherTree.erase(*i);
		}
		end = clock();
		cout << "Erase: execution time for set: " << end - start << " [ms]." << endl;
	}
#endif

	{ // run performance tests on LeBST<string>:
		LeBST<string> tree;

		start = clock();
		for (vector<string>::iterator i = vec.begin(); i != vec.end(); ++i)
		{
			tree.insert(*i);
		}
		end = clock();
		cout << "Insert: execution time for LeBST: " << end - start << " [ms]." << endl;

		start = clock();
		for (vector<string>::iterator i = vec.begin(); i != vec.end(); ++i)
		{
			tree.erase(*i);
		}
		end = clock();
		cout << "Erase: execution time for LeBST: " << end - start << " [ms]." << endl;
	}
}

void performanceTestsOnInts(string dataSource)
{
	// prepare random data:
	cout << endl << "Preparing data from: " << dataSource << endl;

	ifstream in(dataSource, std::ios::in | std::ios::binary);
	vector<string> vec((istream_iterator<string>(in)), istream_iterator<string>());
	in.close();

	vector<int> ints = vector<int>();
	for (vector<string>::iterator i = vec.begin(); i != vec.end(); ++i)
	{
		ints.push_back(atoi((*i).c_str()));
	}

	clock_t start, end;
	cout << endl << "Performance tests for inserting " << ints.size() << " ints :" << endl;

#ifdef BST_TREE_PERFORMANCE_TEST_WITH_SET
	{ // run performance tests on set<int>:
		set<int> otherTree;

		start = clock();
		for (vector<int>::iterator i = ints.begin(); i != ints.end(); ++i)
		{
			otherTree.insert(*i);
		}
		end = clock();
		cout << "Insert: execution time for set: " << end - start << " [ms]." << endl;

		start = clock();
		for (vector<int>::iterator i = ints.begin(); i != ints.end(); ++i)
		{
			otherTree.erase(*i);
		}
		end = clock();
		cout << "Erase: execution time for set: " << end - start << " [ms]." << endl;
	}
#endif

	{ // run performance tests on LeBST<int>:
		LeBST<int> tree;

		start = clock();
		for (vector<int>::iterator i = ints.begin(); i != ints.end(); ++i)
		{
			tree.insert(*i);
		}
		end = clock();
		cout << "Insert: execution time for LeBST: " << end - start << " [ms]." << endl;

		start = clock();
		for (vector<int>::iterator i = ints.begin(); i != ints.end(); ++i)
		{
			tree.erase(*i);
		}
		end = clock();
		cout << "Erase: execution time for LeBST: " << end - start << " [ms]." << endl;
	}

}

void runSimpleTests()
{
	testExtremeCases();
	testDuplicates();

	testIterator();
	
	testInsertUsingModFlags();
	testInsertWithReplace();

	testEraseLeafUsingModFlags();
	testEraseLeafWithReplace();

	testEraseParentUsingModFlags();
}

void runTestScenarios()
{
	testScenarioFromGuideBook();
	testScenarioChainedReplacing();
}

void runPerformanceTests()
{
	srand(time(NULL));

	performanceTestsOnStrings("./../data/lab1.dic");
	performanceTestsOnStrings("./../data/polish.dic");

	performanceTestsOnInts("./../data/numbers.100K.dic");
	performanceTestsOnInts("./../data/numbers.1M.dic");
}

int main()
{
	//LeBST<int, Comparer> tree; // uncomment for tree with inverted order

	runSimpleTests();
	runTestScenarios();
	runPerformanceTests();

	system("pause");
	return 0;
}